package picture;

import java.util.ArrayList;
import java.util.List;

//684. 冗余连接
public class findRedundantConnection {

    public static void main(String[] args) {
//        int[][] edges = new int[][]{{1,3},{1,2},{2,3}};
////                {{9,10},{5,8},{2,6},{1,5},{3,8},{4,9},{8,10},{4,10},{6,8},{7,9}};
//        //[9,10],[5,8],[2,6],[1,5],[3,8],[4,9],[8,10],[4,10],[6,8],[7,9]
//        findRedundantConnection(edges);
    }
    private static int[] roots;
    private static int[] res = new int[2];

    public static int[] findRedundantConnection(int[][] edges) {
        roots = new int[edges.length+1];
        for(int i = 0; i < edges.length+1; i++) {
            roots[i] = i;
        }
        for (int[] edge : edges){
//            unionFind.union(edge[0], edge[1]);
            union(edge[0], edge[1]);
        }
        return res;
    }
    //判断是否成环
    public static int find(int x){
        if(roots[x] != x){
            roots[x] = find(roots[x]);
        }
        return roots[x];
    }
    public static void union(int x, int y){
        int root1 = find(x);
        int root2 = find(y);
        if (root1 != root2){
            roots[root1] = root2;
        }else {
            res[0] = x;
            res[1] = y;
        }
    }

//    class  UnionFind {
//        private static int[] roots;
//
//        public static UnionFind(int size){
//            roots = new int[size];
//            for (int i = 0; i < size; i++){
//                roots[i] = i;
//            }
//        }
//        public static int find(int x){
//            if(roots[x] != x){
//                roots[x] = find(roots[x]);
//            }
//            return roots[x];
//        }
//        public static void union(int x, int y){
//            int root1 = find(x);
//            int root2 = find(y);
//            if (root1 != root2){
//                roots[root1] = root2;
//            }else {
//                res[0] = x;
//                res[1] = y;
//            }
//        }
//    }
}

